\documentclass{article}
\usepackage{amssymb,amsmath} % import math
\usepackage[german]{babel} % import german
\usepackage[applemac]{inputenc} % import german apple
\usepackage{graphicx} % import graphics
\usepackage[babel,german=quotes]{csquotes} % quoting

\usepackage{listings} \lstset{numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\small} 
\lstset{language=Java}
\usepackage[paper=a4paper,left=20mm,right=20mm]{geometry}

\title{HA2 - Uebung 7}
\author{Leonardo Balestrieri, Marco Traeger}

% some newdefs for math symbols
\newcommand{\lfollow}{\rightarrow} % logical follow
\newcommand{\sfollow}{\Longrightarrow} % semantic follow
\newcommand{\siff}{\iff} % semantic iff
\newcommand{\lAnd}[2]{\bigwedge_{#1}^{#2}} % big and
\newcommand{\lOr}[2]{\bigvee_{#1}^{#2}} % big or

\newcommand{\Oc}[2]{\overset{#1}{#2}}
\newcommand{\Uc}[2]{\underset{#1}{#2}}
\newcommand{\OC}[2]{\Oc{#1}{\overbrace{#2}}}
\newcommand{\UC}[2]{\Uc{#1}{\underbrace{#2}}}
\newcommand{\case}[1]{\quad Fall #1 :\\\\}

\begin{document}
\parindent 0pt %keine Zeileneinrueckungen

\maketitle

\section*{7.1a}
Gegeben ein warscheinlicher Text $T$ (z.B. $"$ja$"$ oder $"$nein$"$). Gesucht ist ein Verfahren,
das verhindert das dieser Text durch die Generierung einer Tabelle mit Eintr\"agen 
von Codierungen von wahrscheinlichen Texten entschl\"usselt werden kann.

Wir schlagen vor den Text $T$ k\"unstlich um eine zuf\"allige Folge $Z$ von Buchstaben zu verl\"angern
bis er eine Mindestl\"ange erreicht hat und dann diesen erweiterten Text zu codieren und zu
verschicken.\\
Der Empf\"anger der Nachricht muss jetzt nur noch den Code dekodieren und den Text $T$ von der
zuf\"alligen Erweiterung $Z$ trennen. Da diese Trennung nicht offensichtlich m\"oglich nutzen
wir ein Trennstring $S$, der den Text $T$ und die zuf\"allige Folge $Z$ trennt, dieser Trennstring
ist dabei allen bekannt denen auch der \"offentliche Schl\"ussel bekannt ist.
Dabei ist die einzige Voraussetzung an den Teilstring das er nicht im Text vorkommen darf.

Die neu generierte Nachricht $M_T$ hat dann also die Form.
$$
M_T = TSZ
$$

Dabei ist f\"ur die zuf\"allige Folge $Z$ zu beachten das diese eine bestimme Mindestl\"ange hat.
Annahme $Z$ hat die L\"ange 2 \"uber dem Alphabet $\{0..9\}$ dann gibt es nur $10^2$ verschiedene
Zufallsstrings $Z$, daher kann die vorgeschlagene Tabellenmethode immer noch genutz werden, in dem
alle Codierungen der $10^2$ m\"oglich Erweiterungen $M_T$ der warscheinlichen Nachricht $T$ gespeichert werden.
\medskip

Je L\"anger also der Zufallsstring je sicherer ist die Methode.

\section*{7.2}
$\Sigma = {a_0 \cdots a_k}$. \\

Es gilt $\forall A,B \in \Sigma^{*}: z(AB) \mod (|B| * (k+1)) = z(B)$, \\
daher $z(S) \mod (q * (k+1)$ selektiert die Zahlenrepresentation des Suffix der L\"ange $q$ in $S$. \\

Damit folgt direkt
$$
z(T_{i+1} \cdots T_{i+m}) = z(T_i \cdots T_{i+m}) \mod ((m-1)(k+1))
$$

also
\begin{equation}
\begin{split}
s_{i+1} &= z(T_{i+1} \cdots T_{i+m}) \\
&= z(T_{i+1} \cdots T_{i+m-1})(k+1) + z(T_{i+m}) \\
&= (z(T_i \cdots T_{i+m-1}) \mod ((m-1)(k+1))) (k+1) + z(T_{i+m}) \\
&= z(T_i \cdots T_{i+m-1}) (k+1) \mod (m(k+1)) + z(T_{i+m}) \\
&= s_{i}(k+1) \mod (m(k+1)) + z(T_{i+m})
\end{split}
\end{equation}

Wir k\"onnen $m \cdot (k+1)$ einmal im vorhinein berechnen. \\
Damit kann $s_{i+1}$ aus $s_i$ mit einer Multiplikation, einer Modulorechnung
und einer Addition berechnet werden.
\medskip

Damit k\"onnen wir $s_2 \cdots s_{n-m+1}$ mit $n-m$ Multiplikationen, Modulorechnungen und
Additionen berechnen.

\medskip

Betrachten wir nun, wie wir $s_1$ effizient berechen k\"onnen. \\
Dies ist effizient mit dem Horner-Schema m\"oglich: \\
\begin{equation}
\begin{split}
s_1 &= z(T_i \cdots T_{i+m-1}) \\
&= z(T_i \cdots T_{i+m})(k+1) + z(T_{i+m-1}) \\
&= (z(T_i \cdots T_{i+m+1})(k+1) + z(T_{i+m})) (k+1) + z(T_{i+m-1}) \\
&= ( \cdots (z(T_i) (k+1) + z(T_{i+1})) \cdots ) (k+1) + z(T_{i+m-1})
\end{split}
\end{equation}
Wir ben\"otigen f\"ur die Berechnung von $s_1$ also \\
$m-1$ Multiplikationen und $m-1$ Additionen.

\medskip
Damit ben\"otigen wir insgesamt $n-m+m-1=n-1$ Multiplikationen und Additionen und 
$n-m$ Modulorechnungen. Desweiteren m\"ussen wir $n-m+1$ Vergleiche f\"ur den Vergleich
zwischen $z(P)$ und $s_i$ durchf\"uhren.
\medskip
Damit ist die Laufzeit im Einheitskostenmass 
$$2(n-1) + (n-m) + (n-m+1) = 2(n-1) + 2(n-m) + 1 = 4n - 2m -1$$

\section*{7.3a}
Wir betrachten einen komprimierten Suffixbaum eines Wortes $T \in \Sigma^{*}$ mit $|\Sigma| = k$, $|T| = n$.

\subsection*{Minimale Knotenzahl}
Wir nehmen an das im Text $T$ kein Suffix Pr\"afix eines andren Suffixes ist (er wurde z.B. um ein nicht im
Text vorkommendes Zeichen $\$$ erweitert), denn sonst ist die Betrachtung trivial: 
Wir betrachten das Wort $a^n$ dann ist jeweils $a^i$ Pre\"afix f\"ur alle $a^k$ mit $k > i$.
Damit besteht der Suffixbaum f\"ur $a^n$ nur aus dem Wort $a^n$ und damit enth\"alt der Baum
als einzigen Knoten die Wurzel.
\medskip

Beobachtung: ein Suffixbaum f\"ur einen Text $T$ mit $|T| = n$, wobei kein Suffix Pr\"afix eines anderen Suffizes ist, hat genau n Bl\"atter.
\medskip

Die minimale Knotenzahl wird erreicht, ein Knoten maximal viele Kinder hat, ein Knoten kann nur $k$ Kinder haben,
denn das Alphabet hat Gr\"osse $k$. Damit handelt es sich bei einem Suffixbaum mit minimal vielen inneren Knoten um einen
$k$-n\"aren Baum.

\subsection*{Maximale Knotenzahl}
F\"ur jeden Knoten gilt, er hat mindestens $2$ Kinder, denn sonst w\"are kein Knoten entstanden.
Die Anzahl der inneren Knoten ist maximal wenn jeder innere Knoten minimal viele Kinder hat, also 2.Wie schon betrachtet,
hat der Suffixbaum f\"ur einen Text $T$ mit $|T| = n$ maximal $n$ Bl\"atter.
Damit handelt es sich bei einem Suffixbaum mit maximal vielen inneren Knoten um einen bin\"aren Baum.
Wir k\"onnen also bei $n$ Bl\"attern maximal $n-1$ mal \"uber einen inneren Knoten aufspalten, da bei jedem aufspalten ein 
Blatt mehr entsteht. Damit enth\"alt ein Suffixbaum maximal $n-1$ innere Knoten.

\section*{7.3b}
Betrachten wir alle Suffizes eines Textes $T$ mit $|T| = n$. Dies sind $T_1 \cdots T_n$.
All diese Suffizes bestehen zusammen aus $(n)+(n-1)+ \cdots + (2) + (1) = \frac{n(n-1)}{2}$
Zeichen. 
Wir haben in der vorherigen Aufgabe die Anzahl der Knoten berechnet die maximal ben\"otigt werden um einen Suffixbaum zu speichern,
diese Anzahl liegt in $O(n^2)$, da wir f\"ur jeden Knoten nur konstanten Speicher ben\"otigen liegt der Speicherbedarf f\"ur alle Knoten in
$O(n^2)$. \\
F\"ur alle Suffizes exisiert im Suffixbaum maximal ein Weg von der Wurzel bis zu einem Blatt (kein Weg, wenn der Suffix Prefix eines anderen Suffixes ist.)
Wobei die Kanten dieser Wege nur durch die Zeichen des Suffizes beschrieben sind (die Konkatenation der Kantenbeschriftungen eines
Wegs von der Wurzel zu einem Blatt entspricht einem Suffix des Textes. Daher enth\"ahlt der Suffixbaum maximal $\frac{n(n-1)}{2} \in O(n^2)$ Zeichen
f\"ur die Kantenbeschriftung. \\
Damit ben\"otigen wir insgesamt $O(n^2)$ Speicher um eine Suffixbaum zu speichern.
\medskip

Wir zeigen nun das bei unkomprimierter Beschriftung eines Suffixbaumes man $\Omega(n^2)$
Speicher ben\"oigt.
Wir w\"ahlen das Wort $a^{\lfloor\frac{n}{2}\rfloor} b^{\lceil\frac{n}{2}\rceil}\$$.
F\"ur alle Sequenzen die mit unterschiedlich vielen $a$'s beginnen ist der String $b^{\lceil\frac{n}{2}\rceil}\$$
einmal im Suffixbaum enthalten. Dies sind $\lfloor\frac{n}{2}\rfloor+1$ viele, 
also steht der String $b^{\lceil\frac{n}{2}\rceil}\$$ an $\lfloor\frac{n}{2}\rfloor+1$ verschiedenen Wegen
von der Wurzel zu einem Blatt. \\
Damit ist f\"ur diese Bespiel Speicherplatz von mindestens 
$\lceil\frac{n}{2}\rceil \cdot (\lfloor\frac{n}{2}\rfloor+1) \geq \lceil\frac{n}{2}\rceil^2 \in \Omega(n^2)$ ben\"otigt.

\end{document}